package leetcode.medium.searchmatrix;

/**
 * <a href="https://leetcode.cn/problems/search-a-2d-matrix/description/">74. 搜索二维矩阵</a>
 */
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix.length * matrix[0].length - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (getVal(matrix, mid) == target) {
                return true;
            }
            if (getVal(matrix, mid) > target) {
                j = mid - 1;
                continue;
            }
            i = mid + 1;
        }
        return false;
    }

    private int getVal(int[][] matrix, int idx) {
        int i = idx / matrix[0].length;
        int j = idx % matrix[0].length;
        return matrix[i][j];
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        System.out.println(new Solution().searchMatrix(matrix, 3));
    }
}
